The invention lies in the telecommunications and signal processing fields. More specifically, the invention relates to a method and device for decoding convolutional codes.
In communication systems, for example such as radio systems, the signal to be transmitted (for example voice signal) is submitted to channel coding after conditioning in a source coder. The channel coding serves the purpose of adapting the signal to be transmitted to the properties of the transmission channel. In the process, effective error protection is achieved by specific introduction of redundancy into the signal to be transmitted.
Binary parallel-concatenated recursive convolutional codes have been investigated for channel coding only for a few years. The designation xe2x80x9cturbo codesxe2x80x9d has become established for these convolutional codes. In particular, when transmitting large blocks with more than one thousand bits (symbols), a substantially better error protection can be achieved with turbo codes than with the (conventional) convolutional coding. However, it is disadvantageous that the decoding of turbo codes is more complicated than the decoding of (conventional) convolutional codes.
It has been known to utilize an iterative turbo decoder for the purpose of decoding turbo codes. The iterative turbo decoder thereby contains two individual convolutional decoders which are interleaved with one another in a feedback fashion. At least the convolutional decoder provided on the input side must permit soft decoding, that is to say be capable in the case of each received data symbol to determine in addition to, or instead of, a binary output value a value-continuous estimated value for the original, uncoded data symbol on which the received data symbol is based. It is characteristic of iterative turbo decoders that these value-continuous estimated values are fed to the second convolutional decoder as input information in the course of the iteration. Estimated values for original, uncoded data symbols are also denoted below as a first item of reliability information.
The article xe2x80x9cNear Shannon Limit Error-Correcting, Coding and Decoding: Turbo-codes (1)xe2x80x9d C. Berrou et al., Proc. IEEE Int. Conf. on Communications ICCxe2x80x293, Genua, 1993, pages 1064 to 1070 describes an iterative turbo decoder whose convolutional decoder on the input side is used to produce the first item of reliability information according to a modified Bahl et al.-algorithm. The second convolutional decoder, which need not produce any reliablity information, can operate, for example, according to the known Viterbi algorithm.
Convolutional decoders which operate according to a symbol-by-symbol MAP (maximum a posteriori) algorithm, are likewise capable of producing a first item of reliability information. Such convolutional decoders are denoted as MAP symbol estimator (or else MAP symbol decoder). They have the advantage that they can be used to achieve the lowest possible bit error ratio.
A detailed description of an iterative turbo decoder with two recursively interleaved MAP symbol estimators can be found in the book xe2x80x9cAnalyse und Entwurf digitaler Mobilfunksystemexe2x80x9d [xe2x80x9cAnalysis and Design of Digital Mobile Radio Systemsxe2x80x9d], by P. Jung, Stuttgart, B. G. Teubner, 1997 on pages 343-68, in particular FIG. E.2.
The problem arises in mobile radio applications that the mobile radio channel is highly time variant, that is to say its transmission properties change continuously because of changing environmental influences. The constant changes in the transmission properties of the mobile radio channel must be taken into account as early as during data detection. For this purpose, a communication terminal used in mobile radio has a channel estimator which is coupled to the data detector and continuously determines the transmission properties (pulse responses) of the mobile radio channel and communicates them to the data detector. Such data detection, which takes account of the instantaneous transmission channel properties, is denoted as adaptive data detection or adaptive equalization.
However, the time variance of the mobile radio channel also influences the decoding which takes place downstream of the adaptive equalization. It is disadvantageous in this regard that the high degree of error protection which can in principle be achieved by turbo decoding is nullified again by the time variance of the mobile radio channel, at least in part.
The article xe2x80x9cCombined Turbo Equalization and Turbo Decodingxe2x80x9d by D. Raphaeli and Y. Zarai, IEEE Communications Letters, Vol. 2, No. 4, 1998, pages 107-09 describes an iterative receiver structure which is constructed from a combination of an adaptive equalizer and an (iterative) turbo decoder connected downstream of the latter. The term xe2x80x9cturbo equalizationxe2x80x9d has been coined as keyword for such a combined receiver structure. The iterative turbo decoder is also structured here, in turn, from two MAP symbol decoders. In addition to the first item of reliability information, the two MAP symbol decoders, which are denoted in this article as MAP blocks, also calculate a second item of reliability information. The second item of reliability information constitutes a value-continuous estimated value for the original, coded data symbol on which the detected data symbol is based.
The coupling between adaptive equalization and data decoding is realized by virtue of the fact that in each iteration step the iterative turbo decoder generates from the second item of reliability information of the two convolutional decoders a combined item of reliability information which it feeds to the adaptive equalizer as information which is extrinsic (that is to say not produced in the equalizer itself), and that the adaptive equalizer for its part feeds extrinsic information into the turbo decoder. The time variance of the mobile radio channel can be taken into account during the turbo decoding by means of this feedback between the equalizer and turbo decoder. However, it is disadvantageous that the computational outlay, which is already very high in any case for turbo decoding, is further substantially increased by the fact that the equalizer is also incorporated into the iteration cycle.
A simplified version of an iterative turbo decoder for decoding turbo codes is proposed in the article xe2x80x9cNovel low complexity decoder for turbo-codesxe2x80x9d by P. Jung, Electronics Letters, Vol. 31, No. 2, 1995, pages 86-87. That turbo decoder differs from the previously known turbo decoders in that the two convolutional decoders contained in the turbo decoder operate using a novel, so-called SUBMAP algorithm which, in conjunction with an acceptable deterioration of the decoding performance (that is to say increase in the bit error ratio), permits a substantial saving on computational outlay in the calculation of the first item of reliability information.
In the publication xe2x80x9cCombined turbo equalization and turbo decodingxe2x80x9d, Global Telecommunications Conference (GLOBE-COM), US, New York, IEEE, 1997, pages 639-43, XP00208195 ISBN: 0-7803-4199-6 by Raphaeli et al., a decoder structure is described wherein a sequence of received coded symbols is accepted in accordance with FIG. 3 and the input C1, illustrated there, of the code MAP, a first item of reliability information is calculated for each uncoded symbol in accordance with FIG. 3 and the output L, illustrated therein, of the code MAP block, and a second item of reliability information is calculated for each coded symbol in accordance with FIG. 3 and the output F, illustrated therein, of the code MAP block. Reference is made in the publication to the prior art MAP decoder with reference to determining the second item of reliability information.
A specific modification of the Viterbi decoding algorithm for binary trellis diagrams is proposed in the publication xe2x80x9cSource-controlled Channel Decodingxe2x80x9d in IEEE Transactions on Communications, US, IEEE INC. New York, Vol. 43, No. 9, Sep. 1, 1995 (1995-09-01), pages 2449-57, XP000525669 ISSN: 0090-6778 by J. Hagenauer. The calculation of a second item of reliability information is not taken into account, however, in that case.
The publication xe2x80x9cComprehensive Comparison on Turbo-Code Decodersxe2x80x9d in Proceedings of the Vehicular Technology Conference, US, New York, IEEE, Vol. CONF. 45, 1995, pages 624-28, XP000551609 ISBN: 0-7803-2743-8, by P. Jung et al., discloses a SUB-MAPSSE decoder wherein a second item of reliability information can be determined in a way which is more favorable in terms of outlay.
The object of the present invention is to provide a method and device for decoding convolutional codes which overcome the above-noted deficiencies and disadvantages of the prior art devices and methods of this general kind, and which produce a second item of reliability information for coded transmitted symbols at the output of a convolutional decoder. In particular, the object is for the method to permit a convolutional code to be decoded more favorably in terms of outlay in a receiver structure comprising a combined equalizer and turbo decoder. The further particular object is to configure a convolutional decoder which provides a second item of reliability information for symbols which are transmitted in code, and can be used, in particular, to implement the combined receiver structure.
With the above and other objects in view there is provided, in accordance with the invention, a method of decoding convolutional codes based on a coding process wherein a sequence of coded symbols is produced from a sequence of uncoded symbols by adding redundancy, the method which comprises the steps of:
receiving a sequence of received coded symbols;
calculating a first item of reliability information for each uncoded symbol, wherein the first item of reliability information is representative of a probability that an nth uncoded symbol under consideration of the sequence of uncoded symbols is equal to a value i of the symbol set, on condition that the sequence of received coded symbols is present;
calculating a second item of reliability information for each coded symbol, wherein the second item of reliability information is representative of a probability that a kth coded symbol under consideration of the sequence of coded symbols is equal to a value i of the symbol set, on condition that the sequence of received coded symbols is present, and thereby determining the second item of reliability information substantially by determining a maximum value of code-dependent product terms of the first item of reliability information.
In other words, the second item of reliability information is determined substantially by the determination of the maximum value of code-dependent product terms of the first item of reliability information. This mode of procedure is particularly convenient, since it is only the already determined first item of reliability information which need be used to calculate the second item of reliability information. This is rendered possible because a coded symbol has a property that it can be represented as a sum (dependent on the specific code) over uncoded symbols.
The first item of reliability information can fundamentally be calculated using any desired algorithm, for example the MAP algorithm. Calculation of the first item of reliability information which is favorable in terms of outlay is achieved, in accordance with an added feature of the invention, by first calculating metric increments xcexcn1(E,mxe2x80x2,m), forward recursion values xcex4n(m) and backward recursion values xcex5n+1(mxe2x80x2) with reference to valid transitions between states m, mxe2x80x2 of a coder used in the coding process; and the first item of reliability information is determined by determining maximum values of expressions of the form
{xcex4n(m)+xcexcni(E,mxe2x80x2,m)+xcex5n+1(mxe2x80x2)}, 
wherein i is the value of the nth uncoded symbol.
In accordance with an additional feature of the invention, a-priori knowledge of the sequence of uncoded symbols is present; and the a-priori knowledge is incorporated into the determination of the first and/or second items of reliability information. That is, if there is a priori knowledge of the sequence of the uncoded symbols, this is expediently incorporated into the determination of the first and/or second item of reliability information.
In accordance with another feature of the invention, the sequence of coded symbols is a sequence containing the sequence of uncoded symbols.
With the above and other objects in view there is also provided, in accordance with the invention, a convolutional decoder which incorporates the above-outlined method. The decoder comprises:
a first input for accepting a sequence of received coded symbols;
a first output for outputting a first item of reliability information;
a device configured to calculate the second item of reliability information as outlined above; and
a second output connected to the device for outputting the second item of reliability information.
In accordance with a further feature of the invention, a third output carries, with reference to each uncoded symbol, an estimated value for the uncoded symbol from the symbol set.
In addition to the first output for the first item of reliability information and the second output for the second item of reliability information, the convolutional decoder preferably comprises a third output, at which a xe2x80x9chardxe2x80x9d estimated value, that is to say one contained in the symbol set (in the binary case: 0, 1), is provided for each uncoded symbol.
Because it provides the second item of reliability information in a way which is favorable in terms of computational outlay, the convolutional decoder according to the invention can advantageously be used in a turbo decoder which provides a combined item of reliability information which is formed from the second item of reliability information of a first and a second convolutional decoder.
In order to realize xe2x80x9cturbo equalizationxe2x80x9d, such a turbo decoder is connected up in terms of feedback to an equalizer in such a way that the combined item of reliability information is fed to an input of the equalizer. Because the invention permits a simplified calculation of the combined item of reliability information, turbo equalization is possible with a computational outlay which is sufficiently low for practical applications.
There is thus provided, in accordance with a preferred embodiment of the invention, a turbo decoder, comprising:
first and second convolutional decoders both producing a second item of reliability information, at least one of the first and second convolutional decoders being formed as outlined above;
wherein a first item of reliability information of the first convolutional decoder is fed to the second convolutional decoder as a priori knowledge of a sequence of uncoded symbols;
wherein the first item of reliability information of the second convolutional decoder is fed back to the first convolutional decoder as a priori knowledge of the sequence of the uncoded symbols; and
a logic stage connected to the first and second convolutional decoders for logically combining the second items of reliability information of the first convolutional decoder and of the second convolutional decoder to form a combined item of reliability information.
The turbo decoder is particularly suitable for incorporation in a receiver structure. The turbo decoder is thereby connected to an input of an equalizer in terms of feedback and the equalizer receives from the turbo decoder the combined item of reliability information.
Other features which are considered as characteristic for the invention are set forth in the appended claims.
Although the invention is illustrated and described herein as embodied in a method and device for decoding convolutional codes, it is nevertheless not intended to be limited to the details shown, since various modifications and structural changes may be made therein without departing from the spirit of the invention and within the scope and range of equivalents of the claims.
The construction and method of operation of the invention, however, together with additional objects and advantages thereof will be best understood from the following description of specific embodiments when read in connection with the accompanying drawings.